package com.zp.self.module.level_4_算法练习.数据结构.链表;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_143_重排链表 {
    @Test
    public void main() {

        ListNode node = ListNode.getNode();
        reorderList(node);
        System.out.println(node);

    }

    /**
    题目：给定一个单链表 L 的头节点 head ，单链表 L 表示为：
     L0 → L1 → … → Ln - 1 → Ln
     请将其重新排列后变为：
     L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
     不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

     示例 1：
     输入：head = [1,2,3,4]
     输出：[1,4,2,3]

     示例 2：
     输入：head = [1,2,3,4,5]
     输出：[1,5,2,4,3]

    分析：【P 💔💔💔💔💔】
       1.List+左右指针:将每个节点按顺序存储到list,并将他们的next掰断
                        左右指针再次缝合起来
                --执行用时：2 ms, 在所有 Java 提交中击败了42.59%的用户  --没有灵魂,仅仅是这样的话，你很难无法提升自己
                --时长：12分
       大神：快慢指针： a.利用快慢指针找打中间点
                    b.倒转后半节链表
                    c.重新组装
                --执行用时：1 ms, 在所有 Java 提交中击败了99.95%的用户

    边界值 & 注意点：
       1.
     **/
    public void reorderList(ListNode head) {
        if(head.next==null)return;
        ListNode quickly=head.next,slow=head;
        //找到中间点，偶数则用偏右节点
        while (quickly.next!=null && quickly.next.next!=null){
            slow = slow.next;
            quickly= quickly.next.next;
        }
        quickly = slow.next;
        slow.next=null;
        slow=quickly;
        //反转链表
        ListNode pro = new ListNode(),next;
        pro.next=slow;
        while (slow.next!=null){
            next = slow.next;
            slow.next=next.next;
            next.next=pro.next;
            pro.next = next;
        }
        pro= pro.next;
        //组装链表
        ListNode shang = head;
        head=head.next;
        while (head!=null && pro!=null){
            shang.next =pro;
            pro=pro.next;
            shang=shang.next;
            shang.next=head;
            head=head.next;
            shang=shang.next;
        }
        shang.next=pro;
        // 1.List+左右指针:将每个节点按顺序存储到list,并将他们的next掰断
       /* List<ListNode> list = new ArrayList<>();
        ListNode temp;
        while (head!=null){
            list.add(head);
            temp= head.next ;
            head=temp;
        }
        int left=1,right=list.size()-1;
        temp= list.get(0);
        while (left<=right){
            temp.next =  list.get(right--);
            temp= temp.next;
            if (left<=right) {
                temp.next = list.get(left++);
                temp= temp.next;
            }
        }
        temp.next=null;*/
    }
}
